# -*- coding: utf-8 *-*
'''
@author: Geraldo Oliveira
@date: 13 de abril de 2013
@obs: 
Algoritmo QuickSort
Consultado em:
http://snipt.org/Aaaje2
'''

import math

class QuickSort(object):
    
    def __init__(self, lista):
      '''
      Recebe a lista a ordenar

          lista  -> Lista a ordenar
      '''
      self.lista = lista
 
    def run(self):
        '''
        Inicia o a ordenacao
        '''
        self.qsort_swap(0, len(self.lista))
 
    def qsort_swap(self, begin, end):
        '''
        Algorithmo QuickSort

        Recebe:
            begin -> posicao inicial da lista
            end   -> posicao final da lista
        '''
        if (end - begin) > 1:
           pivot = self.lista[begin]
           l = begin + 1
           r = end
           while l < r:
               if self.lista[l] <= pivot:
                   l += 1
               else:
                   r -= 1
                   self.lista[l], self.lista[r] = self.lista[r], self.lista[l]
           l -= 1
           self.lista[begin], self.lista[l] = self.lista[l], self.lista[begin]    
           self.qsort_swap(begin, l)
           self.qsort_swap(r, end) 
 
    def nome(self):
        '''
        Devolve o nome do metodo de ordenacao
        '''
        return "quicksort"
      
    def o(self, n):
        '''
        Calculo do valor teorico

        Recebe:
            n   -> numero de elementos
        '''
        return (n * math.log(n))

    def __str__(self):
        '''
        Imprime o objecto 
        '''
        return str(self.lista)